package com.yize.tencent;

import org.junit.Test;

/**
 * 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 *
 *
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 *
 * 示例:
 *
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 */
public class DropWater {
    @Test
    public void test(){
        int[] height={0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

    public int trap(int[] height) {
        int maxArea=0;
        if(height.length<3){
            return maxArea;
        }
        int maxPos=0;
        int heightest=Integer.MIN_VALUE;
        for (int i=0;i< height.length;i++){
            if(heightest<height[i]){
                maxPos=i;
                heightest=height[i];
            }
        }
        int left=height[0];
        for (int i=1;i<maxPos;i++){
            if(height[i]<left){
                maxArea+=left-height[i];
            }else {
                left=height[i];
            }
        }

        int right=height[height.length-1];
        for (int i=height.length-2;i>maxPos;i--){
            if(height[i]<right){
                maxArea+=right-height[i];
            }else {
                right=height[i];
            }
        }
        return maxArea;

    }
}
